#define QDataType int
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QInit(Queue*);
void QDestroy(Queue*);
void QPush(Queue*, QDataType);
void QPop(Queue*);
QDataType Qfront(Queue*);
QDataType Qback(Queue*);
QDataType QSize(Queue*);
bool QEmpty(Queue*);

void QInit(Queue* q)
{
	assert(q);
	q->size = 0;
	q->head = q->tail = (QNode*)malloc(sizeof(QNode));
	if (q->head == NULL)
	{
		perror("malloc error");
	}
	q->head->data = 0;
	q->tail->next = NULL;
}

void QDestroy(Queue* q)
{
	while (q->head != NULL)
	{
		QNode* tmp = q->head;
		q->head = q->head->next;
		free(tmp);
	}
	free(q->head);
	q->head = q->tail = NULL;
}

void QPush(Queue* q, QDataType x)
{
	assert(q);
	assert(q->head);
	if (!QEmpty(q))
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		if (newnode == NULL)
		{
			perror("malloc error");
		}
		q->tail->next = newnode;
		q->tail = q->tail->next;
	}
	q->tail->data = x;
	q->tail->next = NULL;
	q->size++;
}

void QPop(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	if (q->size > 1)
	{
		QNode* tmp = q->head;
		q->head = q->head->next;
		free(tmp);
		tmp = NULL;
	}
	q->size--;
}

QDataType Qfront(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->head->data;
}
QDataType Qback(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}
QDataType QSize(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->size;
}
bool QEmpty(Queue* q)
{
	assert(q);
	return !q->size;
}

typedef struct
{
	Queue q1;
	Queue q2;
} MyStack;

MyStack* myStackCreate()
{
	MyStack* s = (MyStack*)malloc(sizeof(MyStack));
	if (s == NULL)
	{
		perror("malloc error");
	}
	QInit(&s->q1);
	QInit(&s->q2);
	return s;
}

void myStackPush(MyStack* obj, int x)
{
	Queue* q = &obj->q1;
	if (QEmpty(&obj->q1))
		q = &obj->q2;
	QPush(q, x);
}

int myStackPop(MyStack* obj)
{
	Queue* qe = &obj->q1;
	Queue* qb = &obj->q2;
	if (QEmpty(&obj->q1))
	{
		qe = &obj->q2;
		qb = &obj->q1;

	}
	while (QSize(qe) > 1)
	{
		QDataType tmp = Qfront(qe);
		QPush(qb, tmp);
		QPop(qe);
	}
	QDataType ret = Qfront(qe);
	QPop(qe);
	return ret;
}

int myStackTop(MyStack* obj)
{
	Queue* qe = &obj->q1;
	Queue* qb = &obj->q1;
	if (QEmpty(&obj->q1))
		qe = &obj->q2;
	return Qback(qe);
}

bool myStackEmpty(MyStack* obj)
{
	return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
	QDestroy(&obj->q1);
	QDestroy(&obj->q2);
	free(obj);
}
